#include "bptree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


struct Record {
	char* str;
};

struct TreeNode {
	char isLeaf; 			/*	1 true, 0 false	*/
	int numKeys;
	int* keys;
	void** pointers;
	pNode parent;
	pNode next;
};

// static int ORDER = DEFAULT_ORDER;
static int ORDER = 5;
static int IS_VERBOSE = FALSE;

/*********************************************/
/*                    utility                */
/*********************************************/
void printLeaves(pNode root ) {
	if (IS_VERBOSE) printf("printLeaves\n");
	assert(root && "printLeaves NULL root");
	pNode node = root;
	while (!node->isLeaf && node->numKeys > 0) {
		node = node->pointers[0];
	}
	if (!node->isLeaf) {
		printf("no leaf node\n");
		return;
	}

	while (node != NULL) {
		printOneLeaf(node);
		node = node->next;
	}
}

void printOneLeaf(pNode leaf) {
	// if (IS_VERBOSE) printf("printOneLeaf\n");
	assert(leaf && "printOneLeaf NULL leaf");
	// printf("-----leaf----\n");
	// printf("numKeys=%d\t", leaf->numKeys);
	int i = 0;
	for (i = 0; i < leaf->numKeys; i++) {
		pRecord rec = (pRecord)(leaf->pointers[i]);
		assert(rec && "should not be NULL");
		printf("%s\t", rec->str);
	}
	printf("\n");
}

void printOneNode(pNode node) {
	assert(node && "printOneNode NULL node");
	int i = 0;
	if (node->isLeaf) {
		// printf("-----leaf----\n");
		printf("numKeys=%d\t", node->numKeys);
		for (i = 0; i < node->numKeys; i++) {
			pRecord rec = (pRecord)(node->pointers[i]);
			assert(rec && "should not be NULL");
			printf("%s\t", rec->str);
		}
	} else {
		printf("-----node----\n");
		printf("numKeys=%d\t", node->numKeys);
		for (i = 0; i < node->numKeys; i++) {
			printf("%c\t", node->keys[i]);
			// printf("%d\t", node->keys[i]);
		}
	}
	printf("\n");
}

/*
** find a leaf node to place "key",
** if not found, return NULL
*/
pNode findLeaf(pNode root, int key) {
	if (IS_VERBOSE) printf("findLeaf\n");
	assert(root && "findLeaf NULL root");
	pNode t = root;

	int i;
	while (!t->isLeaf) {
		/* find the suit child node*/
		if (IS_VERBOSE) {
			printf("all keys\t");
			for (i = 0; i < t->numKeys; i++) printf("%c\t", t->keys[i]);
			// for (i = 0; i < t->numKeys; i++) printf("%d\t", t->keys[i]);
			printf("\n");
		}
		i = 0;
		while (i < t->numKeys && key >= t->keys[i]) {
			// if (IS_VERBOSE) printf("findLeaf : key=%d,key[%d]=%d, find right\n", key, i, root->keys[i]);
			if (IS_VERBOSE) printf("findLeaf : key=%c,key[%d]=%c, find right\n", key, i, root->keys[i]);
			i++;
		}
		t = t->pointers[i];
		assert(t && "t should not be NULL");
	}

	return t;
}

/* find the record node
**
*/
pNode find(pNode root, int key) {
	/* step : find leaf node which may contain the key
	*/
	pNode leaf = findLeaf(root, key);
	if (!leaf) return NULL; /* leaf not found */

	/* step : search in leaf
	*/
	int i;
	for (i = 0; i < leaf->numKeys; i++) {
		if (leaf->keys[i] == key) {
			break; /* found, i< leaf->numKeys */
		}
	}

	if (i < leaf->numKeys) {
		return (pNode)(leaf->pointers[i]);
	} else {
		return NULL;
	}
}

int hash(pRecord rec) {
	char* p = rec->str;
	int t = 0;
	while (*p != NULL) {
		t <<= 5;
		t += *p;
		p++;
	}
	return t;
}

pRecord makeRecord(char* s) {
	pRecord t = malloc(sizeof(struct Record));
	t->str = s;
	return t;
}

pNode makeNode(void) {
	// if (IS_VERBOSE) printf("makeNode\n");
	pNode t = malloc(sizeof(struct TreeNode));
	t->isLeaf = 0;
	t->numKeys = 0;
	t->keys = malloc((ORDER - 1) * sizeof(int));
	t->pointers = malloc((ORDER) * sizeof(void*));
	t->parent = NULL;
	t->next = NULL;
	return t;
}
pNode makeLeaf(void) {
	// if (IS_VERBOSE) printf("makeLeaf\n");
	pNode t = malloc(sizeof(struct TreeNode));
	t->isLeaf = 1;
	t->numKeys = 0;
	t->keys = malloc((ORDER - 1) * sizeof(int));
	t->pointers = malloc((ORDER) * sizeof(void*));
	t->parent = NULL;
	t->next = NULL;
	return t;
}

// start a new tree, and insert a record
pNode startNewTree(int key, pRecord rec) {
	if (IS_VERBOSE) printf("startNewTree\n");
	pNode root = makeLeaf();
	root->numKeys = 1;
	root->keys[0] = key;
	root->pointers[0] = rec;
	root->parent = NULL;
	return root;
}

/* master insert function
**
*/
pNode insert(pNode root, pRecord rec) {
	if (IS_VERBOSE) printf("insert %s\n", rec->str);
	int hashVal = hash(rec);

	/*
	** case 1: tree not exist
	** start a new tree
	*/
	if (root == NULL) {
		return startNewTree(hashVal, rec);
	}

	/*
	** case 2: duplicated
	*/
	if (find(root, hashVal) != NULL) {
		printf("duplicated key, ignore\n");
	}
	/* case 3: tree exists
	*/

	pNode leaf = findLeaf(root, hashVal);
	/* case 3.1: leaf has room */
	if (leaf->numKeys < ORDER - 1) {
		return insertLeaf_notFull(root, leaf, hashVal, rec);
	}
	/* case 3.2: leaf full, must split */
	return insertLeaf_full(root, leaf, hashVal, rec);
}

/*
** leaf not full
*/
pNode insertLeaf_notFull(pNode root, pNode leaf, int key, pRecord rec) {
	if (IS_VERBOSE) printf("insertLeaf_notFull\n");
	assert(leaf && "insertLeaf NULL leaf");
	assert(rec && "insertLeaf NULL rec");
	assert((leaf->numKeys < ORDER - 1 ) && "insertLeaf but leaf full");
	if (IS_VERBOSE) printOneLeaf(leaf);

	// leaf has N keys and N pointers
	int pos = leaf->numKeys;
	while (pos > 0) {
		if (leaf->pointers[pos - 1] == NULL) break;
		if (leaf->keys[pos - 1] >= key) {
			leaf->keys[pos] = leaf->keys[pos - 1] ;
			leaf->pointers[pos] = leaf->pointers[pos - 1] ;
			pos --;
		} else {
			break;
		}
	}
	leaf->pointers[pos] = rec;
	leaf->keys[pos] = key;
	leaf->numKeys++;
	return root;
}

/*
** leaf split
** one full leaf + insert =>
** leafA(left) + leafB(right), midKey
*/
pNode insertLeaf_full(pNode root, pNode leaf, int key, pRecord rec) {
	if (IS_VERBOSE) printf("insertLeaf_full\n");
	assert(root && "insertLeaf_full NULL root");
	assert(leaf && "insertLeaf_full NULL leaf");
	assert(leaf->numKeys == ORDER - 1 && "insertLeaf_full leaf not full");

	pNode newLeaf = makeLeaf();
	int leftCnt = ORDER / 2; // index 0...leftCnt-1
	int rightCnt = ORDER - leftCnt; // rightCnt >= leftCnt
	int i, j;
	if (key < leaf->keys[leftCnt - 1]) {
		/* the rec should stay left,
		** move ORDER - leftCnt => right
		** move rec to left
		*/
		for (i = 0; i < rightCnt; i++) {
			newLeaf->keys[i] = leaf->keys[leftCnt - 1 + i];
			newLeaf->pointers[i] = leaf->pointers[leftCnt - 1 + i];
		}
		for (i = leftCnt - 2; i >= 0; i--) {
			if (leaf->keys[i] > key) {
				leaf->keys[i + 1] = leaf->keys[i];
				leaf->pointers[i + 1] = leaf->pointers[i];
			} else {
				break;
			}
		}
		if (IS_VERBOSE) {
			printf("insertLeaf_full: the rec should stay left\n");
		}
		if (i == -1) i = 0;
		leaf->keys[i] = key;
		leaf->pointers[i] = rec;
	} else {
		if (IS_VERBOSE) {
			printf("insertLeaf_full: the rec should stay right\n");
		}
		/* the rec should stay right
		** move ORDER-1 - leftCnt => right,
		** move rec to right
		*/
		int isInsertKey = 0;
		for (i = 0, j = 0; i < rightCnt - 1; i++) {
			if (!isInsertKey && leaf->keys[leftCnt + i] > key) {
				newLeaf->keys[j] = key;
				newLeaf->pointers[j++] = rec;
				isInsertKey = 1;
			}
			newLeaf->keys[j] = leaf->keys[leftCnt + i];
			newLeaf->pointers[j++] = leaf->pointers[leftCnt + i];
		}
		if (!isInsertKey) {
			newLeaf->keys[j] = key;
			newLeaf->pointers[j] = rec;
		}
	}
	leaf->numKeys = leftCnt;
	newLeaf->numKeys = rightCnt;
	newLeaf->next = leaf->next;
	leaf->next = newLeaf;
	int midKey = newLeaf->keys[0];
	// now re-arrange these keys

	if (IS_VERBOSE) {
		printf("after leaf split\n");
		printf("left\n");
		printOneNode(leaf);
		printf("right\n");
		printOneNode(newLeaf);
	}

	return insertParent(root, leaf, midKey, newLeaf);
}

pNode insertParent(pNode root, pNode left, int  key, pNode right) {
	if (IS_VERBOSE) printf("insertParent\n");
	pNode parent = left->parent;

	/* case 1: new root
	*/
	if (parent == NULL) {
		return insertIntoNewRoot(left, key, right);
	}
	/* case 2: parent not full
	*/
	if (parent->numKeys < ORDER - 1) {
		return insertNode_notFull(root, parent, key, right);
	}
	/* case 3: parent full
	*/
	return insertNode_full(root, parent, key, right);
}

/* Creates a new root for two subtrees
 * and inserts the appropriate key into
 * the new root.
 */
pNode insertIntoNewRoot(pNode left, int  key, pNode right) {
	if (IS_VERBOSE) printf("insertIntoNewRoot\n");
	if (IS_VERBOSE) printf("left\n");
	if (IS_VERBOSE) printOneNode(left);
	if (IS_VERBOSE) printf("right\n");
	if (IS_VERBOSE) printOneNode(right);

	node * root = makeNode();
	root->keys[0] = key;
	root->pointers[0] = left;
	root->pointers[1] = right;
	root->numKeys++;
	root->parent = NULL;
	left->parent = root;
	right->parent = root;
	return root;
}

pNode insertNode_full(pNode root, pNode node, int key, pNode freeNode) {
	if (IS_VERBOSE) printf("insertNode_full\n");
	assert(root && "insertNode_full NULL root");
	assert(node && "insertNode_full NULL node");
	assert(node->numKeys == ORDER - 1 && "insertNode_full node not full");
	if (IS_VERBOSE) {
		printf("node\n");
		printOneNode(node);
		printf("freeNode\n");
		printOneNode(freeNode);
	}

	pNode newNode = makeNode();
	int leftCnt = ORDER / 2; // index 0...leftCnt-1
	int rightCnt = ORDER - leftCnt; // rightCnt >= leftCnt
	int i, j;
	if (key < node->keys[leftCnt - 1]) {
		/* the freeNode should stay left,
		** move ORDER - leftCnt => right
		** move freeNode to left
		*/
		for (i = 0; i < rightCnt; i++) {
			newNode->keys[i] = node->keys[leftCnt - 1 + i];
			newNode->pointers[i] = node->pointers[leftCnt + i];
			((pNode)newNode->pointers[i])->parent = newNode;
		}
		for (i = leftCnt - 2; i >= 0; i--) {
			if (node->keys[i] > key) {
				node->keys[i + 1] = node->keys[i];
				node->pointers[i + 1] = node->pointers[i];
			} else {
				break;
			}
		}
		if (i == -1) i = 0;
		node->keys[i] = key;
		node->pointers[i] = freeNode;
		freeNode->parent = node;
	} else {
		/* the rec should stay right
		** move ORDER-1 - leftCnt => right,
		** move freeNode to right
		*/
		int isInsertKey = 0;
		for (i = 0, j = 0; i < rightCnt - 1; i++) {
			if (!isInsertKey && node->keys[leftCnt + i] > key) {
				newNode->keys[j] = key;
				newNode->pointers[j++] = freeNode;
				isInsertKey = 1;
			}
			newNode->keys[j] = node->keys[leftCnt + i];
			newNode->pointers[j] = node->pointers[leftCnt + 1 + i];
			((pNode)newNode->pointers[j])->parent = newNode;
			j++;
		}
		if (!isInsertKey) {
			newNode->keys[j] = key;
			newNode->pointers[j] = freeNode;
		}
		freeNode->parent = newNode;
	}
	node->numKeys = leftCnt;
	newNode->numKeys = rightCnt - 1;
	int midKey = newNode->keys[0];
	for (i = 0; i < rightCnt - 1; i++) {
		newNode->keys[i] = newNode->keys[i + 1];
	}

	return insertParent(root, node, midKey, newNode);
}

pNode insertNode_notFull(pNode root, pNode node, int key, pNode freeNode) {
	if (IS_VERBOSE) printf("insertNode_notFull\n");
	assert(root && "insertNode_notFull NULL root");
	assert(node && "insertNode_notFull NULL node");
	assert(freeNode && "insertNode_notFull NULL freeNode");
	assert((node->numKeys < ORDER - 1 ) && "insertNode_notFull but node full");
	if (IS_VERBOSE) {
		printf("node\n");
		printOneNode(node);
		printf("freeNode, key=%c\n", key);
		printOneNode(freeNode);
	}
	// node has N keys and N pointers
	int pos = node->numKeys; // point size = pos+1
	while (pos > 0) {
		// if (node->pointers[pos - 1] == NULL) break;
		if (node->keys[pos - 1] > key) {
			node->keys[pos] = node->keys[pos - 1] ;
			node->pointers[pos + 1] = node->pointers[pos] ;
			pos --;
		} else {
			break;
		}
	}
	if (IS_VERBOSE) printf("insertNode_notFull, pos=%d\n", pos);

	node->keys[pos] = key;
	node->pointers[pos + 1] = freeNode;
	node->numKeys++;
	freeNode->parent = node;

	return root;
}
/*********************************************/
/*                   delete                  */
/*********************************************/
// master delete function
pNode delete(pNode root, pRecord rec) {
	printf("delete %s\n", rec->str);
	int hashVal = hash(rec);
	pNode target = find(root, hashVal);
	pNode leaf =  findLeaf(root, hashVal);
	if (target != NULL && leaf != NULL) {
		root = delete_fromNode(root, leaf, target);
		free(target);
	} else {
		printf("delete %s but not found\n", rec->str );
	}
	return root;
}

pNode delete_fromNode(pNode root, pNode node, pNode target) {
	printf("delete_fromNode\n");
	int i;
	int len = node->isLeaf ? node->numKeys : node->numKeys + 1;
	for (i = 0; i < len; i++) {
		if (node->pointers[i] == target) {
			break;
		}
	}
	if (i > len) {
		return root; // target not found in node
	}
	int j;
	if (node->isLeaf) {
		for (j = i; j < node->numKeys; j++) {
			node->keys[j] = node->keys[j + 1];
			node->pointers[j] = node->pointers[j + 1];
		}
	} else {
		for (j = i; j < node->numKeys; j++) {
			if (j - 1 >= 0)
				node->keys[j - 1] = node->keys[j];
		}
		int max = node->numKeys + 1;
		for (j = i; j < max; j++) {
			node->pointers[j] = node->pointers[j + 1];
		}
	}


	node->numKeys --;
	printLeaves(root);


	if (node->parent == NULL) { // root = node
		return root;
	}

	int minKey = (ORDER - 1) / 2;
	// case : full enough
	if (node->numKeys >= minKey) {
		return root;
	}
	// free target ??

	// case : not full enough
	// try borrow, if borrow fail, merge
	pNode parent = node->parent;
	for (i = 0; i < parent->numKeys; i++) {
		if (parent->pointers[i] == node)break;
	}
	// check borrow from left sibling
	int ls_numKeys = -1;
	if (i > 0) {
		pNode ls = (pNode)(parent->pointers[i - 1]);
		ls_numKeys = ls->numKeys;
		if (ls_numKeys >= minKey + 1) {
			return borrowFromSibling(root, node, 1); // 1=left true
		}
	}
	// check borrow from right sibling
	int rs_numKeys = -1;
	if (i < parent->numKeys ) {
		pNode rs = (pNode)(parent->pointers[i + 1]);
		rs_numKeys = rs->numKeys;
		if (rs_numKeys >= minKey + 1) {
			return borrowFromSibling(root, node, 0);
		}
	}

	// fail to borrow, must merge
	printf("ls_numKeys=%d,rs_numKeys=%d\n", ls_numKeys, rs_numKeys);
	if (rs_numKeys > 0) { // merge right
		root = merge(root, node, 0);
	} else { // merge left
		root = merge(root, node, 1);
	}
	return root;
}

// node borrow from left sibling
pNode borrowFromSibling(pNode root, pNode node, int isLeft) {
	printf("borrowFromSibling isLeft=%d\n", isLeft);
	pNode parent = node->parent;
	assert(parent && "borrowFromSibling but parent NULL");
	// parent must not be leaf
	int i, j;
	for (i = 0; i < parent->numKeys + 1; i++) {
		if (parent->pointers[i] == node)break;
	}
	j = i;
	int tmp = isLeft ? -1 : 1;
	pNode sibling = (pNode)(parent->pointers[i + tmp]);
	assert(sibling && "borrowFromSibling but sibling NULL");
	assert((sibling->numKeys >= (ORDER - 1) / 2 + 1) && "borrowFromSibling but sibling not full enough");

	int key_len = sibling->numKeys;
	int pt_len = sibling->isLeaf ? key_len : key_len + 1;
	int key;
	pNode pt;
	if (isLeft) {
		// node add
		if (!node->isLeaf)
			node->pointers[node->numKeys + 1] = node->pointers[node->numKeys];
		for (i = node->numKeys; i > 0; i--) {
			node->keys[i] = node->keys[i - 1];
			node->pointers[i] = node->pointers[i - 1];
		}
		node->keys[0] = sibling->keys[sibling->numKeys - 1];
		int pi = node->isLeaf ? sibling->numKeys - 1 : sibling->numKeys;
		node->pointers[0] = sibling->pointers[pi];
		node->numKeys++;

		//
		sibling->numKeys--;
		// parent
		printf("adjust j=%d, key=%c\n", j, node->keys[0]);
		parent->keys[j - 1] = node->keys[0];

	} else { // brow from right
		// node add
		node->keys[node->numKeys] = sibling->keys[0];
		int pi = node->isLeaf ? node->numKeys : node->numKeys + 1;
		node->pointers[pi] = sibling->pointers[0];
		node->numKeys++;

		// right delete
		for (i = 0; i < sibling->numKeys - 1; i++) {
			sibling->keys[i] = sibling->keys[i + 1];
			sibling->pointers[i] = sibling->pointers[i + 1];
		}
		if (!node->isLeaf) {
			sibling->pointers[sibling->numKeys - 1] = sibling->pointers[sibling->numKeys];
		}
		sibling->numKeys--;
		// parent adjust key;
		printf("adjust j=%d, key=%c\n", j, sibling->keys[0]);
		parent->keys[j] = sibling->keys[0];
	}

	return root;
}

pNode merge(pNode root, pNode node, int isLeft) {
	printf("merge isLeft=%d\n", isLeft);
	pNode parent = node->parent;
	assert(parent && "borrowFromSibling but parent NULL");
	// parent must not be leaf
	int index;
	for (index = 0; index < parent->numKeys + 1; index++) {
		if (parent->pointers[index] == node)break;
	}
	int tmp = isLeft ? -1 : 1;
	pNode sibling = (pNode)(parent->pointers[index + tmp]);

	pNode leftNode = isLeft ? sibling : node;
	pNode rightNode = isLeft ? node : sibling;
	int left_keylen = leftNode->numKeys;
	// merge
	int key_len = sibling->numKeys;
	int i;

	// case : node is leaf
	if (leftNode->isLeaf) {
		for (i = 0; i < rightNode->numKeys; i++) {
			leftNode->keys[left_keylen + i] = rightNode->keys[i];
			leftNode->pointers[left_keylen + i] = rightNode->pointers[i];
		}
		leftNode->numKeys += rightNode->numKeys;
		leftNode->next = rightNode->next;
	} else {
		// case : node is not leaf
		int key = parent->keys[index - 1];
		leftNode->keys[left_keylen] = key;

		for (i = 0; i < rightNode->numKeys; i++) {
			leftNode->pointers[left_keylen + 1 + i ] = rightNode->pointers[i];
			leftNode->keys[left_keylen + 1 + i] = rightNode->keys[i];
		}
		leftNode->pointers[left_keylen + 1 + rightNode->numKeys] = rightNode->pointers[rightNode->numKeys];
	}
	return delete_fromNode(root, parent, rightNode);
}

/*********************************************/
/*                    main                   */
/*********************************************/

void main(void) {
	// test_hash();
	test_create();
}

void test_hash() {
	char* foo = "ab";
	pRecord rec = makeRecord(foo);
	int hv = hash(rec);
	printf("%d\n", hv);
}

void test_create() {
	pNode root = NULL;

	root = insert(root, makeRecord("a"));
	root = insert(root, makeRecord("b"));
	root = insert(root, makeRecord("c"));
	root = insert(root, makeRecord("d"));
	root = insert(root, makeRecord("e"));
	root = insert(root, makeRecord("f"));


	root = insert(root, makeRecord("g"));
	root = insert(root, makeRecord("x"));
	root = insert(root, makeRecord("y"));
	root = insert(root, makeRecord("z"));
	// root = insert(root, makeRecord("z")); // duplicate

	// root = insert(root, makeRecord("h"));
	// root = insert(root, makeRecord("i"));
	// root = insert(root, makeRecord("j"));
	// root = insert(root, makeRecord("k"));
	// root = insert(root, makeRecord("l"));
	// root = insert(root, makeRecord("m"));
	// root = insert(root, makeRecord("n"));
	printLeaves(root);
	// printOneNode(root);
	root = delete(root, makeRecord("c"));
	root = delete(root, makeRecord("f"));
	root = delete(root, makeRecord("e"));
	root = delete(root, makeRecord("g"));
	root = delete(root, makeRecord("x"));

	printLeaves(root);
	printOneNode(root);
}